package com.gy.algorithm.carl.linklistexa;

import com.gy.datastructure.tree.Tree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @BelongsProject: javabase
 * @BelongsPackage: com.gy.algorithm.carl.linklistexa
 * @Author: gy
 * @Date: 2024/10/25 12:00
 * @Description:
 */
public class Flatten114 {


    // 需要思索的
    public static void flatten(TreeNode root) {
         while (root != null){
             if(root.left == null){
                 root = root.right;
             }else{
                 TreeNode pre = root.left;
                 while(pre.right != null){
                     pre = pre.right;
                 }

                 // 将root的原右子树挂到root左子树的最右节点
                 pre.right = root.right;

                 // 将左子树放到右子树
                 root.right = root.left;

                 // 左子树置空
                 root.left = null;

                 root = root.right;
             }
         }
    }

    // 容易想到的
    public static void flatten1(TreeNode root) {
        List<TreeNode> tmp = new ArrayList<>();
        preOrder(root,tmp);
        for (int i = 1; i < tmp.size(); i++) {
            TreeNode pre = tmp.get(i - 1);
            TreeNode cur = tmp.get(i);
            pre.left = null;
            pre.right = cur;
        }
    }

    public static List<TreeNode> preOrder(TreeNode root,List<TreeNode> tmp){
        if(root == null) return tmp;
        tmp.add(root);
        preOrder(root.left,tmp);
        preOrder(root.right,tmp);
        return tmp;
    }
}
